The Scaleable Coherent Interface (SCI) standard for updating cache lines is essentially an invalidate flow, wherein only one cache can have a copy of the line, and this is the copy that will be updated or written, and all other caches must be purged before the write can commence.
A barrier is a mechanism used in parallel processing which will synchronize all processors and/or threads at that point in the code. It is very desirable in parallel processing to have a fast barrier. The faster the barrier, the less time that must be spent on synchronizing, and the more time for performing real work. So a faster barrier allows finer grained parallelism in the system operations. Barriers generally consist of a join and release. The join operation is not covered here because that is generally a fetch and increment instruction. A barrier release is one of the applications that would use write commands involving many nodes trying to read and receive a new value.
FIGS. 1A-C depict a simple SCI sharing list 100 and the actions that are required to actually update or write a value in that list. This assumes that all the nodes that are in the sharing list want to see the new value. In this case, the list 100 has the memory 101, which is marked GONE, meaning that the data in memory is obsolete. The memory includes a pointer that is pointing to node 0 102. The memory pointer is always pointing to the head of the sharing list 100. Thus, as shown in FIG. 1A, node 0 102 is currently the head.
In this case, node 0 102 is marked head.sub.-- dirty, which means that even though the line is shared, node 0 is responsible for returning the data to memory if the sharing list is collasped. Node 0 102, or the head, has a forward pointer that points to node 1 103, which is a mid.sub.-- valid. Node 1 103 has a forward pointer that points to node 2 104, and node 1 103 also a back pointer which points back to node 0 102. Node 2 104 is a tail.sub.-- valid in FIG. 1A, and it has a back pointer to node 1 103.
If node 0 102 wants to increment the value in the line that is shared by the sharing list 100, it must first send a VALID.sub.-- INVALID request to node 1 103. Node 0 102 then receives the forward pointer from the node 1 103, the mid.sub.-- valid node. Node 0 102 uses that forward pointer then to send an invalid request, VALID.sub.-- INVALID to node 2 104. The state received back from node 2 104 is tail, which means that the end of the list has been reached. At that point, node 0 102 is now the only one in the sharing list, and since the list is a dirty list, it can therefore increment the value.
In the meantime, both node 1 103 and node 2 104 are reading the line to see the new value. To read, the nodes must go back to memory 101 and rejoin the sharing list 100. When node 1 103 sends a read request to memory 101, it sees that the line is gone, so memory 101 updates the line to point to node 1 103. Node 1 103 then receives a pointer to node 0 102, which has the only copy of the line. Node 2 104 also sends a read request to memory 101 to rejoin the list. It sees that the memory 101 is gone and that it points to node 1 103 and therefore it has to go to node 1 103 for a new copy of the line. Memory 101 updates its pointer to node 2 104 and then the forward pointer of node 2 104 is changned to node 1 103.
FIG. 1B depicts the state of the cache of the SCI sharing list 100 at the point where the memory 101 is marked GONE and is pointing to node 2 104. Node 2 104 is essentially queued and it is marked queued.sub.-- junk, because the data in the line is not valid. Node 2 104 points to node 1 103, which is also marked queued.sub.-- junk, and node 1 103 points to node 0 102, which has the only valid copy of the line. Thus, at this point node 1 103 sends a cache read request, CREAD, to node 0 102, and receives the new version of the line. Meanwhile, node 2 104 is sending a cache read request to node 1 103. When node 1 103 receives the new value, it will pass the new value to node 2 104, when it receives the next timely request from node 2 104.
FIG. 1C depicts the final state of the sharing list 100. In this case, the memory 101 is marked GONE, and is pointing to node 2 104, which is now marked head, and has valid data. The head, node 2 104, is pointing to node 1 103, which is the mid and has valid data. The mid, node 1 103, is pointing to node 0 102, which was the original writer, and is now the tail.
The main problem with the system and method shown in FIG. 1 is that the sharing list has to be completely disassembled and then rebuilt. This process takes a great deal of system time and resources that otherwise would be available for other transactions.